package trees;

import beans.TreeNode;

import java.util.Stack;

/**
 * 给定一个二叉树，找出其最大深度。
 *
 * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
 *
 * 说明: 叶子节点是指没有子节点的节点。
 *
 * 示例：
 * 给定二叉树 [3,9,20,null,null,15,7]，
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 * 返回它的最大深度 3 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */
public class MaxDepth {
    //dfs
//    public int maxDepth(TreeNode root) {
//        if(root == null){
//            return 0;
//        }
//        maxDepth(root, 0);
//        return max;
//    }
//
//    int max = 0;
//    private void maxDepth(TreeNode root, int depth){
//        if(root == null){
//            if(depth > max){
//                max = depth;
//            }
//            return;
//        }
//        maxDepth(root.left, depth + 1);
//        maxDepth(root.right, depth + 1);
//    }

//    public int maxDepth(TreeNode root){
//        if(root == null){
//            return 0;
//        }
//        int left = maxDepth(root.left);
//        int right = maxDepth(root.right);
//        return Math.max(left, right) + 1;
//    }

    static class Pair<T, E>{
        T first;
        E second;
        Pair(T t, E e){
            first = t;
            second = e;
        }
    }

    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int max = 0;
        int depth = 0;
        Stack<TreeNode> stack = new Stack<>();
        while(!stack.isEmpty() || root != null){
            while(root != null){
                stack.push(root);
                depth ++;
                root = root.left;
            }
            if(depth > max){
                max = depth;
            }
            root = stack.pop();
            depth --;
            root = root.right;
        }
        return max;
    }

}
